﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0060_FindPeakElement : IAlgorithm
    {
        // 162. 寻找峰值

        // 峰值元素是指其值严格大于左右相邻值的元素。
        //给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
        //你可以假设 nums[-1] = nums[n] = -∞ 。
        //你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

        // 提示：
        //  1 <= nums.length <= 1000
        //  -2^31 <= nums[i] <= 2^31 - 1
        //  对于所有有效的 i 都有 nums[i] != nums[i + 1]

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public int FindPeakElement(int[] nums)
        {
            int n = nums.Length;
            int left = 0, right = n - 1, ans = -1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (Compare(nums, mid - 1, mid) < 0 && Compare(nums, mid, mid + 1) > 0)
                {
                    ans = mid;
                    break;
                }
                if (Compare(nums, mid, mid + 1) < 0)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return ans;
        }
        // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
        // 方便处理 nums[-1] 以及 nums[n] 的边界情况
        public int[] Get(int[] nums, int idx)
        {
            if (idx == -1 || idx == nums.Length)
                return new int[] { 0, 0 };
            return new int[] { 1, nums[idx] };
        }
        public int Compare(int[] nums, int idx1, int idx2)
        {
            int[] num1 = Get(nums, idx1);
            int[] num2 = Get(nums, idx2);
            if (num1[0] != num2[0])
                return num1[0] > num2[0] ? 1 : -1;
            if (num1[1] == num2[1])
                return 0;
            return num1[1] > num2[1] ? 1 : -1;
        }

    }
}
